package cxydmmszl.tmp.t5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * <li style="color: red;">Prob</li>
 * 出现次数的 TopK 问题
 * <li style="color: green;">Desc</li>
 * 给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印 出次数前k名的字符串。
 * <br/><br/>[要求]<br/>
 * 如果 strArr 长度为 N，时间复杂度请达到 O(NlogK)
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * ∑字符个数⩽10^5<br/>
 * 1⩽k⩽本质不同的字符串数<br/>
 * 保证输入的字符串仅含有大小写字母/数字
 * <li style="color: green;">Input</li>
 * 第一行两个整数 N, k。N 表示数组大小<br/>
 * 接下来 N 行，每行一个字符串
 * <li style="color: green;">Output</li>
 * 输出K行，每行有一个字符串和一个整数。
 * 你需要按照出现出现次数由小到大输出，若出现次数相同时字符串字典序较小的优先输出。
 * <li style="color: blue;">Link</li> CD84
 *
 * @author habitplus
 * @since 2021-11-02 17:21
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = br.readLine().split(" ");
        int n = Integer.parseInt(ss[0]);
        int k = Integer.parseInt(ss[1]);
        ss = new String[n];
        for (int i = 0; i < n; i++) {
            ss[i] = br.readLine();
        }

        printTopKStrRank(ss, k);

    }

    private static void printTopKStrRank(String[] ss, int k) {
        if (ss == null || ss.length < 1 || k < 1) return;

        Map<String, Integer> cntMap = new HashMap<>();
//        int cnt;
//        for (String s : ss) {
//            cnt = 1;
//            if (cntMap.containsKey(s)) cnt = cntMap.get(s) + 1;
//            cntMap.put(s, cnt);
//        }
        for (String s : ss) {
            cntMap.put(s, cntMap.getOrDefault(s, 0) + 1);
        }

        k = Math.min(k, cntMap.size());
        PriorityQueue<Node> heap = new PriorityQueue<>(cntMap.size(), new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o2.times!= o1.times ? o2.times - o1.times : o1.s.compareTo(o2.s);
            }
        });

        for(Map.Entry<String, Integer> en : cntMap.entrySet()) {
            heap.add(new Node(en.getKey(), en.getValue()));
        }

        StringBuilder sb = new StringBuilder();
        while (k-- > 0) {
            Node node = heap.poll();
            sb.append(node.s).append(" ").append(node.times).append("\n");
        }
        System.out.print(sb.toString());
    }

    static class Node {
        String s;
        int times;

        public Node(String s, int times) {
            this.s = s;
            this.times = times;
        }
    }
}
